package leetcode.dynamic_programming;

/**
 * 53. 最大子数组和
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 * 提示：
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 * 思路: 1.动态规划  O(n)
 * int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
 * 子问题 :
 * 以 -2 结束的连续子数组 最大和是多少
 * 以 1 结束的连续子数组 最大和是多少
 * 以 -3 结束的连续子数组 最大和是多少
 * 以 4 结束的连续子数组 最大和是多少  ...
 * 也就是说我们以每一个节点为结束标识,看以他结束的子数组的最大和是多少
 * 那么就有 第i个元素的结束的最大和为
 * if i-1>=0 nums[i-1]+nums[i] =res[i]
 * else  nums[i] =res[i]
 * 最后我们就得到了一个以每一个元素结束的连续子数组和的一个数组 遍历取最大的一个即可
 */
public class Solution53 {
    public int maxSubArray(int[] nums) {
        // 存放 以i结尾的连续子数组最大和
        int[] res = new int[nums.length];
        res[0] = nums[0];
        int count = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (res[i - 1] >= 0) {
                res[i] = res[i - 1] + nums[i];
            } else {
                res[i] = nums[i];
            }
            count = Math.max(count, res[i]);
        }
        return count;
    }

//    /**
//     * 采用分治的解题
//     *
//     * @param nums
//     * @return
//     */
//    public int maxSubArray2(int[] nums) {
//
//    }

    public static void main(String[] args) {
        Solution53 sol = new Solution53();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        -2 1 - 2 4 3 5 6 - 1 4
        System.out.println(sol.maxSubArray(nums));
    }
}
